//编写一个程序，返回链表中倒数第k个节点
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct ListNode {
    int val;// 节点值
    struct ListNode *next;// 指向下一个节点的指针
};

// 创建新节点
struct ListNode* createNode(int val) {
    // 分配内存并初始化节点
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;// 设置节点值
    newNode->next = NULL;// 初始化下一个节点指针为NULL
    return newNode;// 返回新创建的节点
}

// 返回链表中倒数第k个节点
struct ListNode* getKthFromEnd(struct ListNode* head, int k) {
    if (head == NULL || k <= 0) {// 边界情况处理
        return NULL;
    }
    
    struct ListNode* fast = head;  // 快指针
    struct ListNode* slow = head;  // 慢指针
    
    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            return NULL;  // k大于链表长度
        }
        fast = fast->next;// 快指针前进一步
    }
    
    // 快慢指针同时前进，直到快指针到达链表末尾
    while (fast != NULL) {
        fast = fast->next;// 快指针前进一步
        slow = slow->next;// 慢指针前进一步
    }
    
    return slow;// 返回慢指针所在节点，即倒数第k个节点
}

// 打印链表
void printList(struct ListNode* head) {
    struct ListNode* current = head;// 从头节点开始遍历
    while (current != NULL) {// 遍历链表
        printf("%d", current->val);// 打印当前节点值
        if (current->next != NULL) {// 如果不是最后一个节点，打印箭头
            printf(" -> ");
        }
        current = current->next;// 移动到下一个节点
    }
    printf("\n");
}

// 测试函数
int main() {
    // 创建测试链表: 1 -> 2 -> 3 -> 4 -> 5
    struct ListNode* head = createNode(1);// 创建头节点
    head->next = createNode(2);// 创建第二个节点
    head->next->next = createNode(3);// 创建第三个节点
    head->next->next->next = createNode(4);// 创建第四个节点
    head->next->next->next->next = createNode(5);// 创建第五个节点
    
    printf("链表: ");
    printList(head);// 打印链表
    
    // 测试不同的k值
    int k_values[] = {1, 2, 3, 4, 5};// 测试用例
    int num_tests = sizeof(k_values) / sizeof(k_values[0]);// 计算测试用例数量
    
    for (int i = 0; i < num_tests; i++) {// 遍历测试用例
        int k = k_values[i];// 当前k值
        struct ListNode* result = getKthFromEnd(head, k);// 获取倒数第k个节点
        if (result != NULL) { // 如果节点存在
            printf("倒数第%d个节点: %d\n", k, result->val);// 打印节点值
        } else {
            printf("倒数第%d个节点: 不存在\n", k);
        }
    }
    
    // 测试边界情况
    printf("\n边界情况测试:\n");
    
    // k=0
    struct ListNode* result0 = getKthFromEnd(head, 0);// k为0
    if (result0 == NULL) {// 应返回NULL
        printf("k=0: 返回NULL (正确)\n");// 打印结果
    }
    
    // k大于链表长度
    struct ListNode* result6 = getKthFromEnd(head, 6);// k大于链表长度
    if (result6 == NULL) {// 应返回NULL
        printf("k=6 (大于链表长度): 返回NULL (正确)\n");
    }
    
    // 空链表测试
    struct ListNode* emptyHead = NULL;// 空链表
    struct ListNode* emptyResult = getKthFromEnd(emptyHead, 1);// 测试空链表
    if (emptyResult == NULL) {// 应返回NULL
        printf("空链表测试: 返回NULL (正确)\n");
    }
    
    return 0;// 程序结束
}